#ifndef AVLTREE_H
#define AVLTREE_H
#include <functional>
#include "BSTree.h"

typedef signed char s8;

template<typename T>
class AVLTree : public BSTree<T> {
	protected :
	    class NodeAVL : public BSTree<T>::NodeS {
                public:
                    NodeAVL (T e, u64 k = 0, NodeAVL *l = NULL, NodeAVL *r = NULL)
                             : BSTree<T>::NodeS(e,k,l,r)
                        { _bal = 0; inc = true; }
                    ~NodeAVL () {}
                    int insert(const T&, u64);
                    s8 bal() { return _bal; }
                protected:
                    void rebalance();
                    using BSTree<T>::left;
                    using BSTree<T>::right;
                    using BSTree<T>::_key;
                    using BSTree<T>::multiset;
        	    s8 _bal;
                    bool inc;
	    };
	
        public :	
	    AVLTree ( bool u = false )
                : BSTree<T>(u) {}
            ~AVLTree() {
                if(root)
                    delete root;
            }

	    void insert(const T& e, u64 k = 0) { 
                if (root) 
                    BTree<T>::height += root->insert(e, k);
                else 
                    root = new NodeAVL(e, k, NULL, NULL);
            }

        protected:
            using BSTree<T>::root;
};


#endif /* AVLTREE_H */
